home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / fish / 001-100 / 001-025 / 023 / ver30 / display.c < prev    next >
C/C++ Source or Header  |  1995-03-17  |  20KB  |  766 lines
  1. /*
  2.  * Name:    MicroEMACS
  3.  *        Gosling style redisplay.
  4.  * Version:    30
  5.  * Last edit:    10-Feb-86
  6.  * By:        rex::conroy
  7.  *        decvax!decwrl!dec-rhea!dec-rex!conroy
  8.  *
  9.  * The functions in this file handle redisplay. The
  10.  * redisplay system knows almost nothing about the editing
  11.  * process; the editing functions do, however, set some
  12.  * hints to eliminate a lot of the grinding. There is more
  13.  * that can be done; the "vtputc" interface is a real
  14.  * pig. Two conditional compilation flags; the GOSLING
  15.  * flag enables dynamic programming redisplay, using the
  16.  * algorithm published by Jim Gosling in SIGOA. The MEMMAP
  17.  * changes things around for memory mapped video. With
  18.  * both off, the terminal is a VT52.
  19.  */
  20. #include    "def.h"
  21.  
  22. /*
  23.  * You can change these back to the types
  24.  * implied by the name if you get tight for space. If you
  25.  * make both of them "int" you get better code on the VAX.
  26.  * They do nothing if this is not Gosling redisplay, except
  27.  * for change the size of a structure that isn't used.
  28.  * A bit of a cheat.
  29.  */
  30. #define    XCHAR    int
  31. #define    XSHORT    int
  32.  
  33. /*
  34.  * A video structure always holds
  35.  * an array of characters whose length is equal to
  36.  * the longest line possible. Only some of this is
  37.  * used if "ncol" isn't the same as "NCOL".
  38.  */
  39. typedef    struct    {
  40.     short    v_hash;            /* Hash code, for compares.    */
  41.     short    v_flag;            /* Flag word.            */
  42.     short    v_color;        /* Color of the line.        */
  43.     XSHORT    v_cost;            /* Cost of display.        */
  44.     char    v_text[NCOL];        /* The actual characters.    */
  45. }    VIDEO;
  46.  
  47. #define    VFCHG    0x0001            /* Changed.            */
  48. #define    VFHBAD    0x0002            /* Hash and cost are bad.    */
  49.  
  50. /*
  51.  * SCORE structures hold the optimal
  52.  * trace trajectory, and the cost of redisplay, when
  53.  * the dynamic programming redisplay code is used.
  54.  * If no fancy redisplay, this isn't used. The trace index
  55.  * fields can be "char", and the score a "short", but
  56.  * this makes the code worse on the VAX.
  57.  */
  58. typedef    struct    {
  59.     XCHAR    s_itrace;        /* "i" index for track back.    */
  60.     XCHAR    s_jtrace;        /* "j" index for trace back.    */
  61.     XSHORT    s_cost;            /* Display cost.        */
  62. }    SCORE;
  63.  
  64. int    sgarbf    = TRUE;            /* TRUE if screen is garbage.    */
  65. int    vtrow    = 0;            /* Virtual cursor row.        */
  66. int    vtcol    = 0;            /* Virtual cursor column.    */
  67. int    tthue    = CNONE;        /* Current color.        */
  68. int    ttrow    = HUGE;            /* Physical cursor row.        */
  69. int    ttcol    = HUGE;            /* Physical cursor column.    */
  70. int    tttop    = HUGE;            /* Top of scroll region.    */
  71. int    ttbot    = HUGE;            /* Bottom of scroll region.    */
  72.  
  73. VIDEO    *vscreen[NROW-1];        /* Edge vector, virtual.    */
  74. VIDEO    *pscreen[NROW-1];        /* Edge vector, physical.    */
  75. VIDEO    video[2*(NROW-1)];        /* Actual screen data.        */
  76. VIDEO    blanks;                /* Blank line image.        */
  77.  
  78. #if    GOSLING
  79. /*
  80.  * This matrix is written as an array because
  81.  * we do funny things in the "setscores" routine, which
  82.  * is very compute intensive, to make the subscripts go away.
  83.  * It would be "SCORE    score[NROW][NROW]" in old speak.
  84.  * Look at "setscores" to understand what is up.
  85.  */
  86. SCORE    score[NROW*NROW];
  87. #endif
  88.  
  89. /*
  90.  * Initialize the data structures used
  91.  * by the display code. The edge vectors used
  92.  * to access the screens are set up. The operating
  93.  * system's terminal I/O channel is set up. Fill the
  94.  * "blanks" array with ASCII blanks. The rest is done
  95.  * at compile time. The original window is marked
  96.  * as needing full update, and the physical screen
  97.  * is marked as garbage, so all the right stuff happens
  98.  * on the first call to redisplay.
  99.  */
  100. vtinit()
  101. {
  102.     register VIDEO    *vp;
  103.     register int    i;
  104.  
  105.     ttopen();
  106.     ttinit();
  107.     vp = &video[0];
  108.     for (i=0; i<NROW-1; ++i) {
  109.         vscreen[i] = vp;
  110.         ++vp;
  111.         pscreen[i] = vp;
  112.         ++vp;
  113.     }
  114.     blanks.v_color = CTEXT;
  115.     for (i=0; i<NCOL; ++i)
  116.         blanks.v_text[i] = ' ';
  117. }
  118.  
  119. /*
  120.  * Tidy up the virtual display system
  121.  * in anticipation of a return back to the host
  122.  * operating system. Right now all we do is position
  123.  * the cursor to the last line, erase the line, and
  124.  * close the terminal channel.
  125.  */
  126. vttidy()
  127. {
  128.     ttcolor(CTEXT);
  129.     ttnowindow();                /* No scroll window.    */
  130.     ttmove(nrow-1, 0);            /* Echo line.        */
  131.     tteeol();
  132.     tttidy();
  133.     ttflush();
  134.     ttclose();
  135. }
  136.  
  137. /*
  138.  * Move the virtual cursor to an origin
  139.  * 0 spot on the virtual display screen. I could
  140.  * store the column as a character pointer to the spot
  141.  * on the line, which would make "vtputc" a little bit
  142.  * more efficient. No checking for errors.
  143.  */
  144. vtmove(row, col)
  145. {
  146.     vtrow = row;
  147.     vtcol = col;
  148. }
  149.  
  150. /*
  151.  * Write a character to the virtual display,
  152.  * dealing with long lines and the display of unprintable
  153.  * things like control characters. Also expand tabs every 8
  154.  * columns. This code only puts printing characters into 
  155.  * the virtual display image. Special care must be taken when
  156.  * expanding tabs. On a screen whose width is not a multiple
  157.  * of 8, it is possible for the virtual cursor to hit the
  158.  * right margin before the next tab stop is reached. This
  159.  * makes the tab code loop if you are not careful.
  160.  * Three guesses how we found this.
  161.  */
  162. vtputc(c)
  163. register int    c;
  164. {
  165.     register VIDEO    *vp;
  166.  
  167.     vp = vscreen[vtrow];
  168.     if (vtcol >= ncol)
  169.         vp->v_text[ncol-1] = '$';
  170.     else if (c == '\t') {
  171.         do {
  172.             vtputc(' ');
  173.         } while (vtcol<ncol && (vtcol&0x07)!=0);
  174.     } else if (ISCTRL(c) != FALSE) {
  175.         vtputc('^');
  176.         vtputc(c ^ 0x40);
  177.     } else
  178.         vp->v_text[vtcol++] = c;        
  179. }
  180.  
  181. /*
  182.  * Erase from the end of the
  183.  * software cursor to the end of the
  184.  * line on which the software cursor is
  185.  * located. The display routines will decide
  186.  * if a hardware erase to end of line command
  187.  * should be used to display this.
  188.  */
  189. vteeol()
  190. {
  191.     register VIDEO    *vp;
  192.  
  193.     vp = vscreen[vtrow];
  194.     while (vtcol < ncol)
  195.         vp->v_text[vtcol++] = ' ';
  196. }
  197.  
  198. /*
  199.  * Make sure that the display is
  200.  * right. This is a three part process. First,
  201.  * scan through all of the windows looking for dirty
  202.  * ones. Check the framing, and refresh the screen.
  203.  * Second, make sure that "currow" and "curcol" are
  204.  * correct for the current window. Third, make the
  205.  * virtual and physical screens the same.
  206.  */
  207. VOID update()
  208. {
  209.     register LINE    *lp;
  210.     register WINDOW    *wp;
  211.     register VIDEO    *vp1;
  212.     register VIDEO    *vp2;
  213.     register int    i;
  214.     register int    j;
  215.     register int    c;
  216.     register int    hflag;
  217.     register int    currow;
  218.     register int    curcol;
  219.     register int    offs;
  220.     register int    size;
  221.     VOID traceback ();
  222.     VOID uline ();
  223.  
  224.     if (curmsgf!=FALSE || newmsgf!=FALSE) {
  225.         wp = wheadp;
  226.         while (wp != NULL) {
  227.             wp->w_flag |= WFMODE;    /* Must do mode lines.    */
  228.             wp = wp->w_wndp;
  229.         }
  230.     }
  231.     curmsgf = newmsgf;            /* Sync. up right now.    */
  232.     hflag = FALSE;                /* Not hard.        */
  233.     wp = wheadp;
  234.     while (wp != NULL) {
  235.         if (wp->w_flag != 0) {        /* Need update.        */
  236.             if ((wp->w_flag&WFFORCE) == 0) {
  237.                 lp = wp->w_linep;
  238.                 for (i=0; i<wp->w_ntrows; ++i) {
  239.                     if (lp == wp->w_dotp)
  240.                         goto out;
  241.                     if (lp == wp->w_bufp->b_linep)
  242.                         break;
  243.                     lp = lforw(lp);
  244.                 }
  245.             }
  246.             i = wp->w_force;    /* Reframe this one.    */
  247.             if (i > 0) {
  248.                 --i;
  249.                 if (i >= wp->w_ntrows)
  250.                     i = wp->w_ntrows-1;
  251.             } else if (i < 0) {
  252.                 i += wp->w_ntrows;
  253.                 if (i < 0)
  254.                     i = 0;
  255.             } else
  256.                 i = wp->w_ntrows/2;
  257.             lp = wp->w_dotp;
  258.             while (i!=0 && lback(lp)!=wp->w_bufp->b_linep) {
  259.                 --i;
  260.                 lp = lback(lp);
  261.             }
  262.             wp->w_linep = lp;
  263.             wp->w_flag |= WFHARD;    /* Force full.        */
  264.         out:
  265.             lp = wp->w_linep;    /* Try reduced update.    */
  266.             i  = wp->w_toprow;
  267.             if ((wp->w_flag&~WFMODE) == WFEDIT) {
  268.                 while (lp != wp->w_dotp) {
  269.                     ++i;
  270.                     lp = lforw(lp);
  271.                 }
  272.                 vscreen[i]->v_color = CTEXT;
  273.                 vscreen[i]->v_flag |= (VFCHG|VFHBAD);
  274.                 vtmove(i, 0);
  275.                 for (j=0; j<llength(lp); ++j)
  276.                     vtputc(lgetc(lp, j));
  277.                 vteeol();
  278.             } else if ((wp->w_flag&(WFEDIT|WFHARD)) != 0) {
  279.                 hflag = TRUE;
  280.                 while (i < wp->w_toprow+wp->w_ntrows) {
  281.                     vscreen[i]->v_color = CTEXT;
  282.                     vscreen[i]->v_flag |= (VFCHG|VFHBAD);
  283.                     vtmove(i, 0);
  284.                     if (lp != wp->w_bufp->b_linep) {
  285.                         for (j=0; j<llength(lp); ++j)
  286.                             vtputc(lgetc(lp, j));
  287.                         lp = lforw(lp);
  288.                     }
  289.                     vteeol();
  290.                     ++i;
  291.                 }
  292.             }
  293.             if ((wp->w_flag&WFMODE) != 0)
  294.                 modeline(wp);
  295.             wp->w_flag  = 0;
  296.             wp->w_force = 0;
  297.         }        
  298.         wp = wp->w_wndp;
  299.     }
  300.     lp = curwp->w_linep;            /* Cursor location.    */
  301.     currow = curwp->w_toprow;
  302.     while (lp != curwp->w_dotp) {
  303.         ++currow;
  304.         lp = lforw(lp);
  305.     }
  306.     curcol = 0;
  307.     i = 0;
  308.     while (i < curwp->w_doto) {
  309.         c = lgetc(lp, i++);
  310.         if (c == '\t')
  311.             curcol |= 0x07;
  312.         else if (ISCTRL(c) != FALSE)
  313.             ++curcol;
  314.         ++curcol;
  315.     }
  316.     if (curcol >= ncol)            /* Long line.        */
  317.         curcol = ncol-1;
  318.     if (sgarbf != FALSE) {            /* Screen is garbage.    */
  319.         sgarbf = FALSE;            /* Erase-page clears    */
  320.         epresf = FALSE;            /* the message area.    */
  321.         tttop  = HUGE;            /* Forget where you set    */
  322.         ttbot  = HUGE;            /* scroll region.    */
  323.         tthue  = CNONE;            /* Color unknown.    */
  324.         ttmove(0, 0);
  325.         tteeop();
  326.         for (i=0; i<nrow-1; ++i) {
  327.             uline(i, vscreen[i], &blanks);
  328.             ucopy(vscreen[i], pscreen[i]);
  329.         }
  330.         ttmove(currow, curcol);
  331.         ttflush();
  332.         return;
  333.     }
  334. #if    GOSLING
  335.     if (hflag != FALSE) {            /* Hard update?        */
  336.         for (i=0; i<nrow-1; ++i) {    /* Compute hash data.    */
  337.             hash(vscreen[i]);
  338.             hash(pscreen[i]);
  339.         }
  340.         offs = 0;            /* Get top match.    */
  341.         while (offs != nrow-1) {
  342.             vp1 = vscreen[offs];
  343.             vp2 = pscreen[offs];
  344.             if (vp1->v_color != vp2->v_color
  345.             ||  vp1->v_hash  != vp2->v_hash)
  346.                 break;
  347.             uline(offs, vp1, vp2);
  348.             ucopy(vp1, vp2);
  349.             ++offs;
  350.         }
  351.         if (offs == nrow-1) {        /* Might get it all.    */
  352.             ttmove(currow, curcol);
  353.             ttflush();
  354.             return;
  355.         }
  356.         size = nrow-1;            /* Get bottom match.    */
  357.         while (size != offs) {
  358.             vp1 = vscreen[size-1];
  359.             vp2 = pscreen[size-1];
  360.             if (vp1->v_color != vp2->v_color
  361.             ||  vp1->v_hash  != vp2->v_hash)
  362.                 break;
  363.             uline(size-1, vp1, vp2);
  364.             ucopy(vp1, vp2);
  365.             --size;
  366.         }
  367.         if ((size -= offs) == 0)    /* Get screen size.    */
  368.             abort();
  369.         setscores(offs, size);        /* Do hard update.    */
  370.         traceback(offs, size, size, size);
  371.         for (i=0; i<size; ++i)
  372.             ucopy(vscreen[offs+i], pscreen[offs+i]);
  373.         ttmove(currow, curcol);
  374.         ttflush();
  375.         return;            
  376.     }
  377. #endif
  378.     for (i=0; i<nrow-1; ++i) {        /* Easy update.        */
  379.         vp1 = vscreen[i];
  380.         vp2 = pscreen[i];
  381.         if ((vp1->v_flag&VFCHG) != 0) {
  382.             uline(i, vp1, vp2);
  383.             ucopy(vp1, vp2);
  384.         }
  385.     }
  386.     ttmove(currow, curcol);
  387.     ttflush();
  388. }
  389.  
  390. /*
  391.  * Update a saved copy of a line,
  392.  * kept in a VIDEO structure. The "vvp" is
  393.  * the one in the "vscreen". The "pvp" is the one
  394.  * in the "pscreen". This is called to make the
  395.  * virtual and physical screens the same when
  396.  * display has done an update.
  397.  */
  398. ucopy(vvp, pvp)
  399. register VIDEO    *vvp;
  400. register VIDEO    *pvp;
  401. {
  402.     register int    i;
  403.  
  404.     vvp->v_flag &= ~VFCHG;            /* Changes done.    */
  405.     pvp->v_flag  = vvp->v_flag;        /* Update model.    */
  406.     pvp->v_hash  = vvp->v_hash;
  407.     pvp->v_cost  = vvp->v_cost;
  408.     pvp->v_color = vvp->v_color;
  409.     for (i=0; i<ncol; ++i)
  410.         pvp->v_text[i] = vvp->v_text[i];
  411. }
  412.  
  413. /*
  414.  * Update a single line. This routine only
  415.  * uses basic functionality (no insert and delete character,
  416.  * but erase to end of line). The "vvp" points at the VIDEO
  417.  * structure for the line on the virtual screen, and the "pvp"
  418.  * is the same for the physical screen. Avoid erase to end of
  419.  * line when updating CMODE color lines, because of the way that
  420.  * reverse video works on most terminals.
  421.  */
  422. VOID uline(row, vvp, pvp)
  423. VIDEO    *vvp;
  424. VIDEO    *pvp;
  425. {
  426. #if    MEMMAP
  427.     putline(row+1, 1, &vvp->v_text[0]);
  428. #else
  429.     register char    *cp1;
  430.     register char    *cp2;
  431.     register char    *cp3;
  432.     register char    *cp4;
  433.     register char    *cp5;
  434.     register int    nbflag;
  435.  
  436.     if (vvp->v_color != pvp->v_color) {    /* Wrong color, do a    */
  437.         ttmove(row, 0);            /* full redraw.        */
  438.         ttcolor(vvp->v_color);
  439.         cp1 = &vvp->v_text[0];
  440.         cp2 = &vvp->v_text[ncol];
  441.         while (cp1 != cp2) {
  442.             ttputc(*cp1++);
  443.             ++ttcol;
  444.         }
  445.         return;
  446.     }
  447.     cp1 = &vvp->v_text[0];            /* Compute left match.    */
  448.     cp2 = &pvp->v_text[0];
  449.     while (cp1!=&vvp->v_text[ncol] && cp1[0]==cp2[0]) {
  450.         ++cp1;
  451.         ++cp2;
  452.     }
  453.     if (cp1 == &vvp->v_text[ncol])        /* All equal.        */
  454.         return;
  455.     nbflag = FALSE;
  456.     cp3 = &vvp->v_text[ncol];        /* Compute right match.    */
  457.     cp4 = &pvp->v_text[ncol];
  458.     while (cp3[-1] == cp4[-1]) {
  459.         --cp3;
  460.         --cp4;
  461.         if (cp3[0] != ' ')        /* Note non-blanks in    */
  462.             nbflag = TRUE;        /* the right match.    */
  463.     }
  464.     cp5 = cp3;                /* Is erase good?    */
  465.     if (nbflag==FALSE && vvp->v_color==CTEXT) {
  466.         while (cp5!=cp1 && cp5[-1]==' ')
  467.             --cp5;
  468.         /* Alcyon hack */
  469.         if ((int)(cp3-cp5) <= tceeol)
  470.             cp5 = cp3;
  471.     }
  472.     /* Alcyon hack */
  473.     ttmove(row, (int)(cp1-&vvp->v_text[0]));
  474.     ttcolor(vvp->v_color);
  475.     while (cp1 != cp5) {
  476.         ttputc(*cp1++);
  477.         ++ttcol;
  478.     }
  479.     if (cp5 != cp3)                /* Do erase.        */
  480.         tteeol();
  481. #endif
  482. }
  483.  
  484. /*
  485.  * Redisplay the mode line for
  486.  * the window pointed to by the "wp".
  487.  * This is the only routine that has any idea
  488.  * of how the modeline is formatted. You can
  489.  * change the modeline format by hacking at
  490.  * this routine. Called by "update" any time
  491.  * there is a dirty window.
  492.  */
  493. modeline(wp)
  494. register WINDOW    *wp;
  495. {
  496.     register char    *cp;
  497.     register int    c;
  498.     register int    n;
  499.     register BUFFER    *bp;
  500.  
  501.     n = wp->w_toprow+wp->w_ntrows;        /* Location.        */
  502.     vscreen[n]->v_color = CMODE;        /* Mode line color.    */
  503.     vscreen[n]->v_flag |= (VFCHG|VFHBAD);    /* Recompute, display.    */
  504.     vtmove(n, 0);                /* Seek to right line.    */
  505.     bp = wp->w_bufp;
  506.     if ((bp->b_flag&BFCHG) != 0)        /* "*" if changed.    */
  507.         vtputc('*');
  508.     else
  509.         vtputc(' ');
  510.     n  = 1;
  511.     cp = "MicroEMACS";            /* Buffer name.        */
  512.     while ((c = *cp++) != 0) {
  513.         vtputc(c);
  514.         ++n;
  515.     }
  516.     if (bp->b_bname[0] != 0) {
  517.         vtputc(' ');
  518.         ++n;
  519.         cp = &bp->b_bname[0];
  520.         while ((c = *cp++) != 0) {
  521.             vtputc(c);
  522.             ++n;
  523.         }
  524.     }
  525.     if (bp->b_fname[0] != 0) {        /* File name.        */
  526.         vtputc(' ');
  527.         ++n;
  528.         cp = "File:";
  529.         while ((c = *cp++) != 0) {
  530.             vtputc(c);
  531.             ++n;
  532.         }
  533.         cp = &bp->b_fname[0];
  534.         while ((c = *cp++) != 0) {
  535.             vtputc(c);
  536.             ++n;
  537.         }
  538.     }
  539.     if (curmsgf != FALSE            /* Message alert.    */
  540.     && wp->w_wndp == NULL) {
  541.         while (n < ncol-5-1) {
  542.             vtputc(' ');
  543.             ++n;
  544.         }
  545.         cp = "[Msg]";            /* Sizeof("[Msg]") = 5.    */
  546.         while ((c = *cp++) != 0) {
  547.             vtputc(c);
  548.             ++n;
  549.         }
  550.     }
  551.     while (n < ncol) {            /* Pad out.        */
  552.         vtputc(' ');
  553.         ++n;
  554.     }
  555. }
  556.  
  557. #if    GOSLING
  558. /*
  559.  * Compute the hash code for
  560.  * the line pointed to by the "vp". Recompute
  561.  * it if necessary. Also set the approximate redisplay
  562.  * cost. The validity of the hash code is marked by
  563.  * a flag bit. The cost understand the advantages
  564.  * of erase to end of line. Tuned for the VAX
  565.  * by Bob McNamara; better than it used to be on
  566.  * just about any machine.
  567.  */
  568. hash(vp)
  569. register VIDEO    *vp;
  570. {
  571.     register int    i;
  572.     register int    n;
  573.     register char    *s;
  574.  
  575.     if ((vp->v_flag&VFHBAD) != 0) {        /* Hash bad.        */
  576.         s = &vp->v_text[ncol-1];
  577.         for (i=ncol; i!=0; --i, --s)
  578.             if (*s != ' ')
  579.                 break;
  580.         n = ncol-i;            /* Erase cheaper?    */
  581.         if (n > tceeol)
  582.             n = tceeol;
  583.         vp->v_cost = i+n;        /* Bytes + blanks.    */
  584.         for (n=0; i!=0; --i, --s)
  585.             n = (n<<5) + n + *s;
  586.         vp->v_hash = n;            /* Hash code.        */
  587.         vp->v_flag &= ~VFHBAD;        /* Flag as all done.    */
  588.     }
  589. }
  590.  
  591. /*
  592.  * Compute the Insert-Delete
  593.  * cost matrix. The dynamic programming algorithm
  594.  * described by James Gosling is used. This code assumes
  595.  * that the line above the echo line is the last line involved
  596.  * in the scroll region. This is easy to arrange on the VT100
  597.  * because of the scrolling region. The "offs" is the origin 0
  598.  * offset of the first row in the virtual/physical screen that
  599.  * is being updated; the "size" is the length of the chunk of
  600.  * screen being updated. For a full screen update, use offs=0
  601.  * and size=nrow-1.
  602.  *
  603.  * Older versions of this code implemented the score matrix by
  604.  * a two dimensional array of SCORE nodes. This put all kinds of
  605.  * multiply instructions in the code! This version is written to
  606.  * use a linear array and pointers, and contains no multiplication
  607.  * at all. The code has been carefully looked at on the VAX, with
  608.  * only marginal checking on other machines for efficiency. In
  609.  * fact, this has been tuned twice! Bob McNamara tuned it even
  610.  * more for the VAX, which is a big issue for him because of
  611.  * the 66 line X displays.
  612.  *
  613.  * On some machines, replacing the "for (i=1; i<=size; ++i)" with
  614.  * i = 1; do { } while (++i <=size)" will make the code quite a
  615.  * bit better; but it looks ugly.
  616.  */
  617. setscores(offs, size)
  618. {
  619.     register SCORE    *sp;
  620.     register int    tempcost;
  621.     register int    bestcost;
  622.     register int    j;
  623.     register int    i;
  624.     register VIDEO    **vp;
  625.     register VIDEO    **pp;
  626.     register SCORE    *sp1;
  627.     register VIDEO    **vbase;
  628.     register VIDEO    **pbase;
  629.  
  630.     vbase = &vscreen[offs-1];        /* By hand CSE's.    */
  631.     pbase = &pscreen[offs-1];
  632.     score[0].s_itrace = 0;            /* [0, 0]        */
  633.     score[0].s_jtrace = 0;
  634.     score[0].s_cost   = 0;
  635.     sp = &score[1];                /* Row 0, inserts.    */
  636.     tempcost = 0;
  637.     vp = &vbase[1];
  638.     for (j=1; j<=size; ++j) {
  639.         sp->s_itrace = 0;
  640.         sp->s_jtrace = j-1;
  641.         tempcost += tcinsl;
  642.         tempcost += (*vp)->v_cost;
  643.         sp->s_cost = tempcost;
  644.         ++vp;
  645.         ++sp;
  646.     }
  647.     sp = &score[NROW];            /* Column 0, deletes.    */
  648.     tempcost = 0;
  649.     for (i=1; i<=size; ++i) {
  650.         sp->s_itrace = i-1;
  651.         sp->s_jtrace = 0;
  652.         tempcost  += tcdell;
  653.         sp->s_cost = tempcost;
  654.         sp += NROW;
  655.     }
  656.     sp1 = &score[NROW+1];            /* [1, 1].        */
  657.     pp = &pbase[1];
  658.     for (i=1; i<=size; ++i) {
  659.         sp = sp1;
  660.         vp = &vbase[1];
  661.         for (j=1; j<=size; ++j) {
  662.             sp->s_itrace = i-1;
  663.             sp->s_jtrace = j;
  664.             bestcost = (sp-NROW)->s_cost;
  665.             if (j != size)        /* Cd(A[i])=0 @ Dis.    */
  666.                 bestcost += tcdell;
  667.             tempcost = (sp-1)->s_cost;
  668.             tempcost += (*vp)->v_cost;
  669.             if (i != size)        /* Ci(B[j])=0 @ Dsj.    */
  670.                 tempcost += tcinsl;
  671.             if (tempcost < bestcost) {
  672.                 sp->s_itrace = i;
  673.                 sp->s_jtrace = j-1;
  674.                 bestcost = tempcost;
  675.             }
  676.             tempcost = (sp-NROW-1)->s_cost;
  677.             if ((*pp)->v_color != (*vp)->v_color
  678.             ||  (*pp)->v_hash  != (*vp)->v_hash)
  679.                 tempcost += (*vp)->v_cost;
  680.             if (tempcost < bestcost) {
  681.                 sp->s_itrace = i-1;
  682.                 sp->s_jtrace = j-1;
  683.                 bestcost = tempcost;
  684.             }
  685.             sp->s_cost = bestcost;
  686.             ++sp;            /* Next column.        */
  687.             ++vp;
  688.         }
  689.         ++pp;
  690.         sp1 += NROW;            /* Next row.        */
  691.     }
  692. }
  693.  
  694. /*
  695.  * Trace back through the dynamic programming cost
  696.  * matrix, and update the screen using an optimal sequence
  697.  * of redraws, insert lines, and delete lines. The "offs" is
  698.  * the origin 0 offset of the chunk of the screen we are about to
  699.  * update. The "i" and "j" are always started in the lower right
  700.  * corner of the matrix, and imply the size of the screen.
  701.  * A full screen traceback is called with offs=0 and i=j=nrow-1.
  702.  * There is some do-it-yourself double subscripting here,
  703.  * which is acceptable because this routine is much less compute
  704.  * intensive then the code that builds the score matrix!
  705.  */
  706. VOID traceback(offs, size, i, j)
  707. {
  708.     register int    itrace;
  709.     register int    jtrace;
  710.     register int    k;
  711.     register int    ninsl;
  712.     register int    ndraw;
  713.     register int    ndell;
  714.  
  715.     if (i==0 && j==0)            /* End of update.    */
  716.         return;
  717.     itrace = score[(NROW*i) + j].s_itrace;
  718.     jtrace = score[(NROW*i) + j].s_jtrace;
  719.     if (itrace == i) {            /* [i, j-1]        */
  720.         ninsl = 0;            /* Collect inserts.    */
  721.         if (i != size)
  722.             ninsl = 1;
  723.         ndraw = 1;
  724.         while (itrace!=0 || jtrace!=0) {
  725.             if (score[(NROW*itrace) + jtrace].s_itrace != itrace)
  726.                 break;
  727.             jtrace = score[(NROW*itrace) + jtrace].s_jtrace;
  728.             if (i != size)
  729.                 ++ninsl;
  730.             ++ndraw;
  731.         }
  732.         traceback(offs, size, itrace, jtrace);
  733.         if (ninsl != 0) {
  734.             ttcolor(CTEXT);
  735.             ttinsl(offs+j-ninsl, offs+size-1, ninsl);
  736.         }
  737.         do {                /* B[j], A[j] blank.    */
  738.             k = offs+j-ndraw;
  739.             uline(k, vscreen[k], &blanks);
  740.         } while (--ndraw);
  741.         return;
  742.     }
  743.     if (jtrace == j) {            /* [i-1, j]        */
  744.         ndell = 0;            /* Collect deletes.    */
  745.         if (j != size)
  746.             ndell = 1;
  747.         while (itrace!=0 || jtrace!=0) {
  748.             if (score[(NROW*itrace) + jtrace].s_jtrace != jtrace)
  749.                 break;
  750.             itrace = score[(NROW*itrace) + jtrace].s_itrace;
  751.             if (j != size)
  752.                 ++ndell;
  753.         }
  754.         if (ndell != 0) {
  755.             ttcolor(CTEXT);
  756.             ttdell(offs+i-ndell, offs+size-1, ndell);
  757.         }
  758.         traceback(offs, size, itrace, jtrace);
  759.         return;
  760.     }
  761.     traceback(offs, size, itrace, jtrace);
  762.     k = offs+j-1;
  763.     uline(k, vscreen[k], pscreen[offs+i-1]);
  764. }
  765. #endif
  766.